Branching quantifier

In logic a branching quantifier,[1] also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering[2]

\langle Qx_1\dots Qx_n\rangle

of quantifiers for Q∈{∀,∃}. It is a special case of generalized quantifier. In classical logic, quantifier prefixes are linearly ordered such that the value of a variable ym bound by a quantifier Qm depends on the value of the variables

y1,...,ym-1

bound by quantifiers

Qy1,...,Qym-1

preceding Qm. In a logic with (finite) partially ordered quantification this is not in general the case.

Branching quantification first appeared in Leon Henkin's "Some Remarks on Infinitely Long Formulas", Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 1959. Systems of partially ordered quantification are intermediate in strength between first-order logic and second-order logic. They are being used as a basis for Hintikka's and Gabriel Sandu's independence-friendly logic (also known as informational-independence logic) which are claimed to be the most natural logics as a foundations for mathematics (e.g. set theory) or for capturing certain features of natural language and epistemology.

Contents

Definable Quantifiers

The simplest Henkin quantifier Q_H is

(Q_Hx_1,x_2,y_1,y_2)\phi(x_1,x_2,y_1,y_2)\equiv\begin{pmatrix}\forall x_1 \exists y_1\\ \forall x_2 \exists y_2\end{pmatrix}\phi(x_1,x_2,y_1,y_2).

It (in fact every formula with a Henkin prefix, not just the simplest one) is equivalent to its second-order Skolemization, i.e.

\exists f \exists g \forall x_1 \forall x_2\phi (x_1,x_2,f(x_1),g(x_2)).

It is also powerful enough to define the quantifier Q_{\geq\mathbb{N}} (i.e. "there are infinitely many") defined as

(Q_{\geq\mathbb{N}}x)\phi (x)\equiv\exists a(Q_Hx_1,x_2,y_1,y_2)[\phi a\land (x_1=x_2 \leftrightarrow y_1=y_2) \land (\phi (x_1)\rightarrow (\phi (y_1)\land y_1\neq a))].

Several things follow from this, including the nonaxiomatizability of first-order logic with Q_H and its equivalence to the \Sigma_1^1-fragment of second-order logic.

The following quantifiers are also definable by Q_H.

Rescher: "The number of φs is less than or equal to the number of ψs"

(Q_Lx)(\phi x,\psi x)\equiv Card(\{ x \colon\phi x\} )\leq Card(\{ x \colon\psi x\} ) \equiv (Q_Hx_1x_2y_1y_2)[(x_1=x_2 \leftrightarrow y_1=y_2) \land (\phi x_1 \rightarrow \psi y_1)]

Härtig: "The φs are equinumerous with the ψs"

(Q_Ix)(\phi x,\psi x)\equiv (Q_Lx)(\phi x,\psi x) \land (Q_Lx)(\psi x,\phi x)

Chang: "The number of φs is equinumerous with the domain of the model"

(Q_Cx)(\phi x)\equiv (Q_Lx)(x=x,\phi x)

See also

References

  1. ^ Stanley Peters; Dag Westerståhl (2006). Quantifiers in language and logic. Clarendon Press. pp. 66–72. ISBN 9780199291250. http://books.google.com/books?id=fc8U900Oh2oC&pg=PA66. 
  2. ^ Antonio Badia (2009). Quantifiers in Action: Generalized Quantification in Query, Logical and Natural Languages. Springer. p. 74. ISBN 9780387095639. http://books.google.com/books?id=WC4pkt3m5b0C&pg=PA74. 

External links